// 注意如果精度不够，可以改成i64那个P去做，但是时间复杂度要慢很多
namespace Convolution {
  constexpr double PI = acos(-1);
  using i64 = long long;
  using i128 = __int128_t;
  // const i64 p = 31525197391593473ll, G = 6;
  const int p = 998244353, G = 3;
  vector<i64> R;

  int power(int a, int b) {
    int ret = 1;
    while (b > 0) {
      if (b & 1) {
        ret = (i64)ret * a % p;
      }
      a = (i64)a * a % p;
      b >>= 1;
    }
    return ret;
  }

  int inv(int x) {
    return power(x, p - 2);
  }

  void rev(vector<int> &A, int len) {
    for(int i = 0;i < len; ++ i) {
      if(i < R[i]) {
        swap(A[i], A[R[i]]);
      }
    }
  }

  void ntt(vector<int> &A, int op) {
    int len = A.size();
    rev(A, len);
    for(int mid = 1; mid < len; mid <<= 1) {//原根代替单位根
      int wn = power(G, (p - 1) / (mid * 2));
      if(op == -1) {
        wn = power(wn, p - 2);
      }
      for(int l = mid << 1, pos = 0; pos < len; pos += l) {
        int w = 1;
        for(int k = 0; k < mid; ++ k, w = ((i64)w * wn) % p) {
          i64 x = A[pos + k], y = (i64) w * A[pos + mid + k] % p;
          A[pos + k] = ((i64)x + y) % p;
          A[pos + k + mid] = ((i64)x - y + p) % p;
        }
      }
		}
	if(op == -1) {
      i64 len_inv = inv(len);// len的逆元
      for(int i = 0; i < len; ++i) {
        A[i] = ((i64)A[i] * len_inv) % p;//NTT还是要除以n的，但是这里把除换成逆元了，inv就是n在模p意义下的逆元
      }
    }
  }

vector<int> NTT(vector<int> &A, vector<int> &B) {
    int n = A.size(), m = B.size();
    int Bm = n + m, Bn = 1;
    while (Bn < Bm) {
        Bn <<= 1;
    }
    R.resize(Bn + 1);
    for (int i = 0; i < Bn; ++i) {
        R[i] = (R[i >> 1] >> 1) + ((i & 1) ? Bn >> 1 : 0);
    }
    while (A.size() < Bn) {
      A.emplace_back(0);
    }
    while (B.size() < Bn) {
      B.emplace_back(0);
    }
    ntt(A, 1); ntt(B, 1);
    for (int i = 0; i < Bn; ++i) {
    	A[i] = (i64)A[i] * B[i] % p;
    }
    ntt(A, -1);
    vector<int> ret;
    int s = 0;
    for (int i = 0; i < A.size(); i++) {
      s += A[i] % p;
      ret.push_back(s % 10);
      s /= 10;
    }
    while (s > 0) {
      ret.push_back(s % 10);
      s /= 10;
    }
    while (ret.size() > 1 && ret.back() == 0) {
      ret.pop_back();
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
}